package demo_0405;

import java.util.HashSet;
import java.util.Set;

public class T1 {
    /*给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，
    其余每个元素均出现两次。找出那个只出现了一次的元素。

    1 <= nums.length <= 3 * 104
    -3 * 104 <= nums[i] <= 3 * 104
    除了某个元素只出现一次以外，其余每个元素均出现两次。
    */

    // 方法一
    // 遍历数组，把每个元素都放到set中
    // 遍历数组，判断set中是否包含这个元素
    // 如果包含，就从set中删除
    // 如果不包含，就把这个元素放到set中
    // 遍历结束，set中就只剩下一个元素
    // 把这个元素返回
    // 时间复杂度：O(n)
    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int tmp : nums) {
            if (set.contains(tmp)) {
                set.remove(tmp);
            }else {
                set.add(tmp);
            }
        }
        for (int tmp : nums) {
            if (set.contains(tmp)) {
                return tmp;
            }
        }
        return -1;
    }

    /*    方法二
    *   遍历数组，把每个元素都异或起来
    *   遍历数组，把每个元素都异或起来
    *   遍历结束，得到的结果就是只出现一次的元素
    *   时间复杂度：O(n)
    * */

    public int singleNumber1(int[] nums) {
        int tmp = 0;
        for(int i = 0; i < nums.length; i++) {
            tmp ^= nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] ^ tmp) == 0) {
                return nums[i];
            }
        }
        return -1;
    }
}
